package 优先算法.递归_搜索与回溯.初学递归.汉诺塔问题;


import java.util.ArrayList;
import java.util.List;

/**
 *https://leetcode.cn/problems/hanota-lcci/description/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        List<Integer> A = new ArrayList<Integer>();
        List<Integer> B = new ArrayList<Integer>();
        List<Integer> C = new ArrayList<Integer>();
        A.add(2);
        A.add(1);
        A.add(0);


        so.hanota(A,B,C);
        System.out.println("A:"+A+"B:"+B+"C:"+C );
    }
}
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }
    public static void dfs(List<Integer> Star, List<Integer> Mid, List<Integer> End,int n){

        if(n==1){
            End.add(Star.remove(Star.size()-1));
            return;
        }
        dfs(Star,End,Mid,n-1);
        End.add(Star.remove(Star.size()-1) );
        dfs(Mid,Star,End,n-1);
    }
}
